import java.util.Stack;

//二叉树的最近公共祖先
class Solution2 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //法一
        /*if(root == null){
            return null;
        }
        if(root == p || root == q){
            return root;
        }
        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
        if(leftTree != null && rightTree != null){
            return root;
        }else if(leftTree != null){
            return leftTree;
        }else{
            return rightTree;
        }
        */

        //法二

        if(root == null ) return null;
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();

        getPath(root,p,stackP);
        getPath(root,q,stackQ);

        int sizeP = stackP.size();
        int sizeQ = stackQ.size();

        if(sizeP > sizeQ){
            int size = sizeP - sizeQ;
            while(size != 0){
                stackP.pop();
                size--;
            }
        }else{
            int size = sizeQ - sizeP;
            while(size != 0){
                stackQ.pop();
                size--;
            }
        }
        //两个栈当中元素一样多
        while(!stackP.isEmpty() && !stackQ.isEmpty()){
            if(stackP.peek() == stackQ.peek()){
                return stackP.peek();
            }else{
                stackP.pop();
                stackQ.pop();
            }
        }
        return null;

    }
    private boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){
        if(root == null || node == null){
            return false;
        }
        stack.push(root);
        if(root == node){
            return true;
        }
        boolean flg = getPath(root.left,node,stack);
        if(flg ){
            return true;
        }
        boolean flg2 = getPath(root.right,node,stack);
        if(flg2){
            return true;
        }
        stack.pop();
        return false;
    }
}class Solution2 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //法一
        /*if(root == null){
            return null;
        }
        if(root == p || root == q){
            return root;
        }
        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
        if(leftTree != null && rightTree != null){
            return root;
        }else if(leftTree != null){
            return leftTree;
        }else{
            return rightTree;
        }
        */

        //法二

        if(root == null ) return null;
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        
        getPath(root,p,stackP);
        getPath(root,q,stackQ);

        int sizeP = stackP.size();
        int sizeQ = stackQ.size();

        if(sizeP > sizeQ){
            int size = sizeP - sizeQ;
            while(size != 0){
                stackP.pop();
                size--;
            }
        }else{
             int size = sizeQ - sizeP;
            while(size != 0){
                stackQ.pop();
                size--;
            }
        }
        //两个栈当中元素一样多
        while(!stackP.isEmpty() && !stackQ.isEmpty()){
            if(stackP.peek() == stackQ.peek()){
                return stackP.peek();
            }else{
                stackP.pop();
                stackQ.pop();
            }
        }
        return null;

    }
      private boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){
            if(root == null || node == null){
            return false;
        }
        stack.push(root);
        if(root == node){
            return true;
        }
        boolean flg = getPath(root.left,node,stack);
        if(flg ){
            return true;
        }
        boolean flg2 = getPath(root.right,node,stack);
        if(flg2){
            return true;
        }
        stack.pop();
        return false;
    }
}